import java.util.ArrayList;
//import java.util.Collections;
import java.util.Scanner;

/**
 *
 * @
 */
public class Graph {


        int[][] matrix = {{0,8,4,0,2},
                        {8,0,0,10,0},
                        {4,0,0,12,0},
                        {0,10,12,0,1},
                        {2,0,0,1,0}

        };
        ArrayList<Edge> edges = new ArrayList<Edge>();
        ArrayList<String> nodes = new ArrayList<String>();


        public Graph() {

                for(int i = 0; i < matrix.length; i++) {
                        nodes.add(Integer.toString(i));
                        for (int j=0;j<i;j++) {
                                if (matrix[i][j]>0) {
                                        String name = i + "-" + j;
                    boolean // <editor-fold defaultstate="collapsed" desc="comment">
                            add// </editor-fold>
 = edges.add(new Edge(name, matrix[i][j]));
                                }
                        }
                }

        }
        //--------------------------------------------------------------------------------------------
        // author Navid Ranjbar, Mahdi Abdinejadi, Amirhossein Tayarani
        public void dijkstra () {
                int index = 0;
                int previousIndex = 0;
                int minIndex = 0;
                int tempNode [] = new int[nodes.size()];
                int distance [] = new int [nodes.size()]; // array for distances
                String path [] = new String[nodes.size()];
                int indexArray = nodes.size();

                for(int i = 0; i < nodes.size(); i++) {
                        tempNode[i] = i;
                }
                // getting source from user
                Scanner scan = new Scanner(System.in);
                for(int i = 0; i < nodes.size(); i++)
                        System.out.print(nodes.get(i) + ", ");
                System.out.println();
                System.out.println("enter the source node from nodes above:");
                String startNode = scan.next();
                for(int i = 0; i < nodes.size(); i++)
                        if(nodes.get(i).equalsIgnoreCase(startNode)){
                                index = i;
                                break;
                        }


                distance = initializeSingleSource(distance, index);

                while(indexArray > 0) { // finding minimum distance in distances array
                        for(int i = 0, min = 1000; i < distance.length; i++) {
                                if (tempNode[i] != -1 && distance[i] < min) { // set flag for seprating the nodes that we already covers
                                        min = distance[i];
                                        minIndex = i;



                                }
                        }
                        // setting path
                        path[minIndex] = nodes.get(previousIndex);
                        if (indexArray ==  nodes.size())
                                path[minIndex] = "no way";


                        distance = relax(distance, minIndex);
                        previousIndex = minIndex;

                        tempNode[minIndex] = -1;
                        indexArray--;


                }
                // geting destination from user
                scan = new Scanner(System.in);
                for(int i = 0; i < nodes.size(); i++)
                        System.out.print(nodes.get(i) + ", ");
                System.out.println();
                System.out.println("enter the destination node from nodes above:");
                String destination = scan.next();
                for(int i = 0; i < nodes.size(); i++)
                        if(nodes.get(i).equalsIgnoreCase(destination)){
                                index = i;
                                break;
                        }

                        System.out.println("distance = " + distance[index]);

                System.out.println("--------------------");
                System.out.println("this is the path array printed, we didn't have time to format it the correct way");
                for(int i = 0; i < distance.length; i++){


                        System.out.println(path[i]);
                }

                System.out.println("-------------------------------------------------------");
        }
        //---------------------------------------------------------------
        // author Pooyan Mobtahej, Hadi Oliazadeh
        public int[] initializeSingleSource(int[] dis, int index){
                for (int i = 0; i < dis.length; i++)
                        dis[i] = 1000; // a number that we think is bigger than every other weight

                dis[index] = 0;

                return dis;
        }
        //------------------------------------------------------------------------------
        // author Pooyan Mobtahej, Hadi Oliazadeh
        public int[] relax(int[] dis, int minimum) {
                for(int i = 0; i < dis.length; i++) {
                        if (matrix[i][minimum] > 0  && dis[i] > dis[minimum] + matrix[i][minimum]) {
                                dis[i] = dis[minimum] + matrix[i][minimum];
                        }
                }

                return dis;
        }
        //-----------------------------------------------------------------------------------
        // author Navid Ranjbar, Amir hossein Tayarani, hadi Oliazadeh
        public void MST() {
                int edgeCount = 1;
                int [][] tempMatrix = new int[matrix.length][matrix.length];
                for(int i = 0; i < matrix.length; i++)
                        for(int j = 0; j < matrix.length; j++){
                                tempMatrix[i][j] = matrix[i][j];
                                if(tempMatrix[i][j] > 0)
                                        edgeCount++;
                        }
                edgeCount = edgeCount/2;
                int[] max = {-1,-1};

                while(edgeCount > 0 ){
                        int maxValue = -1;
                        // finding the max weighted edge
                        for(int i = 0; i < tempMatrix.length; i++)
                                for(int j = 0; j < tempMatrix.length; j++)
                                        if(tempMatrix[i][j] > maxValue){
                                                maxValue = tempMatrix[i][j];
                                                max[0] = i;
                                                max[1] = j;
                                        }
                        tempMatrix[max[0]][max[1]] = 0;
                        tempMatrix[max[1]][max[0]] = 0;
                        if(!(isConnected(tempMatrix))){ // setting flag for the edge that removing them resulting the graph to get disconnected
                                tempMatrix[max[0]][max[1]] = -1;
                                tempMatrix[max[1]][max[0]] = -1;
                        }
                        edgeCount--;// counter to keep track of iteration
                }
                for(int i = 0; i < tempMatrix.length; i++) //setting flag edge to previous value from the source adjacancy matrix
                        for(int j = 0; j < tempMatrix.length; j++)
                                if(tempMatrix[i][j] == -1)
                                        tempMatrix[i][j] = matrix[i][j];
                System.out.println("Minimum Spanning Tree's Ajacancy Matrix:");
                for(int i = 0; i < tempMatrix.length; i++){ // printing the adjacancy matrix
                        System.out.println();
                        for(int j = 0; j < tempMatrix.length; j++){
                                System.out.print(tempMatrix[i][j]+",");
                        }
                }
        }

        //---------------------------------------------------------------
// author Mahdi Abdinejadi, Cyrus Sedaghat, Pooyan Mobtahej
        public boolean isConnected(int [][]source){ // check from the adjacacncy matrix that if the graph is connected or not
                int temp = 0;
                ArrayList<Integer> reachable = new ArrayList<Integer>();
                ArrayList<Integer> tempNodes = new ArrayList<Integer>();
                ArrayList<Integer> nodes2 = new ArrayList<Integer>();

                for( int i = 0; i < source.length;i++){
                        tempNodes.add(i);
                        nodes2.add(i);
                }

                int counter = 0;
                while(counter < nodes2.size()){ // adding the adjacant nodes to array list
                        for (int i=0; i < source.length; i++){
                                if (source[temp][i]> 0){
                                        if (!reachable.contains(i) && tempNodes.contains(i))
                                                reachable.add(i);
                                }
                        }
                        tempNodes.remove(tempNodes.indexOf(temp));
                        if (reachable.isEmpty())
                                break;
                        temp = reachable.get(0);
                        reachable.remove(0);
                        if ( tempNodes.isEmpty())
                                break;
                        counter++;
                }

                if (tempNodes.isEmpty())
                        return true;
                else
                        return false;

        }


        //------------------------------------------------------------------

        public static void main(String args[]) {
                Graph graph = new Graph();
                graph.dijkstra();
                graph.MST();

        }
}

